#define _CRT_SECURE_NO_WARNINGS 1
class Partition {
public:
	ListNode* partition(ListNode* head, int x) {
		if (head == nullptr) {
			return nullptr;
		}
		ListNode* smallList = new ListNode(-1);
		ListNode* bigList = new ListNode(-1);
		ListNode* ps = smallList, * pb = bigList, * cur = head;
		while (cur) {
			if (cur->val < x) {
				ps->next = cur;
				ps = cur;
			}
			else {
				pb->next = cur;
				pb = cur;
			}
			cur = cur->next;
		}
		pb->next = nullptr;
		ps->next = bigList->next;
		return smallList->next;
	}
};